//
//  Stack.hpp
//  stack
//
//  Created by chenyh on 2021/2/4.
//

#ifndef Stack_hpp
#define Stack_hpp

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
/**
 定义栈的数据结构，要求添加一个 min()函数，能
 够得到栈的最小元素。要求函数 min()、push()及 pop()函数的时 间复杂度都是 O(1)。
 该题的目的是要考察对栈数据结构的深入理解。要 实现题目的要求，需要对栈数据结构进行改进。我们可以设置一个变量 min 来存储栈中数 据最小的值。因为栈中所有的元素都是大于或等于该元素作为栈顶时的最小元素值 min， 所以可以在栈中不存储原始的元素值，而存储元素值与最小值 min 之间的差值。在入栈时， 如果原始的元素值比当前最小值 min 大，则将 nmin 入栈，此时栈中为正值。如果发现此 时入栈的元素比当前最小值 min 小，则将它们的差值入栈，此时为负值，同时用当前入栈 值更新 min。整理一下这种思路可以得到下面的步骤。
 (1)对 push()函数修改:首先在入栈时，如果当前入栈的值 n<当前最小值 min，更新 min 的值为 n 的值，将 nmin 的值入栈;否则直接将 nmin 的值入栈。
 (2)相应的对 pop()函数进行修改:如果栈顶元素 top≤0，则说明此时的原始栈顶元素 为当前最小元素 min，则出栈时，直接弹出当前的最小值 min，同时更新 min 值为 mintop; 如果栈顶元素 top>0，则 pop()函数返回 top+min 为原始元素值。
 (3)对于 min()函数来说，只需要返回 min 就可以了。整体来看，这 3 个函数都满足 了时间复杂度为 O(1)的要求。
 */
template<typename DataType> class Stack
{
    
public:
    vector<DataType> value; //定义栈结构使用vector存储元素
    DataType m_min;         //存储最小值的变量
public:
    const DataType& min();
    void pop();
    void push(const DataType &n);
    void prinValue();       //获取栈顶元素值
    bool isEmpty();         //判断栈是否为空
};

// 获取最小值的函数
template <typename DataType> const DataType& Stack<DataType>:: min()
{
    assert(!value.empty());//如果栈空，则推出
    return m_min;
}

template <typename DataType> void Stack<DataType>::push(const DataType &n)
{
    if (value.empty()) { //如果栈空，则更新最小值
        m_min = n;
    }
    //计算入栈元素与最小值的差值
    DataType diff = n - m_min;
    value.push_back(diff);  //差值入栈
    if (diff < 0) {
        m_min = n;  //如果差值小于0，则更新最小值
    }
    
}
template <typename DataType> void Stack<DataType>::pop()
{
    assert(!value.empty()); //
    DataType top = value.back();//获取栈顶值
    if (top < 0) {
        m_min-=top; //如果栈顶值为负，则更新最小值
    }
    value.pop_back();//弹出元素
}
template <typename DataType> void Stack<DataType>::prinValue()
{
    assert(!value.empty());
    DataType originValue;
    DataType top = value.back();
    if (top < 0) {
        originValue = m_min;
    }
    else
    {
        originValue = (top) + m_min;
    }
    cout<<originValue;
}
template <typename DataType> bool Stack<DataType>::isEmpty()
{
    if (value.empty()) {
        return true;
    }else {
        return false;
    }
    
}


#endif /* Stack_hpp */
